cryptographyfandomcom-20200215-history
Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if p'' is prime and ''a is coprime to p'', then ''ap''−1 − 1 is divisible by ''p. If a composite integer x'' is coprime to an integer ''a > 1 and x'' divides ''ax''−1 − 1, then ''x is called a Fermat pseudoprime to base a''. In other words, a composite integer is a Fermat pseudoprimes to base ''a if it successfully passes Fermat primality test for the base a''. The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes Fermat primality test for the base 2. Pseudoprimes to base 2 are called '''Poulet numbers' or sometimes Sarrus numbers or Fermatians . An integer x'' that is a Fermat pseudoprime for all values of ''a that are coprime to x'' is called a Carmichael number. Variations Some sources use variations of the definition, for example to only allow odd numbers to be pseudoprimes. Every odd number ''q satisfies a^{q-1} \equiv 1 \pmod q for a=q-1 . This trivial case is excluded in the definition of a Fermat pseudoprime given by Crandall and Pomerance: :A composite number q'' is a Fermat pseudoprime to a base ''a, if a^{q-1} \equiv 1 \pmod q and 2 \le a \le q-2. This stronger definition excludes every power of three (9, 27, 81, 243, ...), and many even integers from the base-2 Fermat pseudoprimes. Properties Distribution There are infinitely many pseudoprimes to a given base (in fact, infinitely many Carmichael numbers), but they are rather rare. There are only three pseudo-primes to base 2 below 1000, and below a million there are only 245. Factorizations The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the below table. | | | |} A Poulet number all of whose divisors d'' divide 2''d − 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers. Smallest Fermat pseudoprimes The smallest pseudoprime for each base a'' ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below ''a are excluded in the table. Euler–Jacobi pseudoprimes Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler–Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay–Strassen primality test and the Miller–Rabin primality test, which produce what are known as industrial-grade primes. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure. Applications The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test. References External links *W. F. Galway, Database of Base-2 Pseudoprimes up to 10^15 (including Strong Pseudoprimes and Carmichael numbers) Category:Pseudoprimes Category:Asymmetric-key cryptosystems de:Fermatsche Pseudoprimzahl